package code;


public class RegularExpression {

	public boolean isMatchII(String s,String p){
		int i,j,k;
		int n=s.length();
		int m=p.length();
		if(n==0 || m==0){
			if(n==m)	return true;
			return false;
		}
		boolean[][] isOk=new boolean[n+1][m+1];
		/*
		 * ��ʼ����isOk[0][0]=true
		 */
		isOk[0][0]=true;
		if(m>1 && p.charAt(1)=='*'){
			isOk[0][2]=true;
		}
		
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				isOk[i+1][j+1]=false;
				if(p.charAt(j)!='*' && p.charAt(j)!='.'){
					if(p.charAt(j)==s.charAt(i))
						isOk[i+1][j+1]=isOk[i][j];
				}
				else if(p.charAt(j)=='*'){
					/*
					 * a*,��ʾ��0������1�����ϵ�a�ַ�
					 */
					isOk[i+1][j+1]=isOk[i+1][j];
					if(isOk[i+1][j+1])	continue;
					for(k=i;k>=0 && (s.charAt(k)==p.charAt(j-1) || p.charAt(j-1)=='.');k--)
						if(isOk[k][j]){
							isOk[i+1][j+1]=true;
							break;
						}
				}
				else if(p.charAt(j)=='.'){
					isOk[i+1][j+1]=isOk[i][j];
				}
//				System.out.println(s.charAt(i)+" "+p.charAt(j)+"  "+isOk[i+1][j+1]);
			}
		}
		for(i=1;i<=m;i++){
			for(j=1;j<=n;j++)
			if(isOk[n][i])	return true;
		}
		return isOk[n][m];
	}
	/*
	 * �����bug̫���ˣ�д��̫���������ɹٷ��Ľⷨ���ݹ����
	 * ��p[j]����*,��ô�ͱȽ�s[i],��p[j]
	 * ��p[j]��*,��ô�ݹ����
	 */
	
	public boolean isGood(String s,String p){
		//��������
		if(p.length()==0)
			return s.length()==0;
		if(p.length()==1){
			if(s.length()<1)
				return false;
			if(p.charAt(0)!=s.charAt(0) && p.charAt(0)!='.')
				return false;
			return isGood(s.substring(1),p.substring(1));
		}
		if(p.charAt(1)!='*'){
			if(s.length()<1)	return false;
			if(p.charAt(0)!=s.charAt(0) && p.charAt(0)!='.')
				return false;
			return isGood(s.substring(1),p.substring(1));
		}
		else{
			if(isGood(s,p.substring(2)))
				return true;
			int i=0;
			while(i<s.length() && (s.charAt(i)==p.charAt(0) || p.charAt(0)=='.')){
				if(isGood(s.substring(i+1),p.substring(2)))
					return true;
				i++;
			}
		}
		return false;
	}
	public boolean isMatch(String s,String p){
		return isGood(s,p); 
	}
	
	public String nomalizied(String str){
		if(str.length()==0)	return str;
		int i=0,j;
		while(i<str.length()){
			if((str.charAt(i)>='0' && str.charAt(i)<='9') || str.charAt(i)=='-' || str.charAt(i)=='+')
			break;
			i++;
		}
		j=str.length()-1;
		while(j>=0){
			if((str.charAt(i)>='0' && str.charAt(i)<='9')) break;
			j--;
		}
		return str.substring(i,j+1);
	}
	public int atoi(String str){
		int x=0;
		int sign=1;
		str=nomalizied(str);
		if(str.length()==0)	return 0;
		if(str.charAt(0)=='+'){
			sign=1;
			str=str.substring(1);
		}
		else if(str.charAt(0)=='-'){
			sign=-1;
			str=str.substring(1);
		}
		if(str.length()>0 && str.charAt(0)>='0' && str.charAt(0)<='9'){
			for(int i=0;i<str.length();i++){
				if(str.charAt(i)<'0' && str.charAt(i)>'9') break;
				x*=10;
				x+=(int)(str.charAt(i)-'0');
			}
			return x*sign;
		}
		return 0;
	}
	public static void main(String[] args){
		String s="aaa";
		String p="ab*ac*a";
		RegularExpression re=new RegularExpression();
		System.out.println(re.isMatch(s, p));
		
		System.out.println(re.atoi("   010a"));
	}
}
